//
//  XBBinTree.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/22.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBBinTree.h"
#include "XBLinkList.h"

// -- 二叉树的形态
/*

 空，只有根节点，只有左子树或者右子树，两个都有
 
 特殊性形态：1.斜树，都只在左或右侧有节点
           2.满二叉树:所有的分支节点都存在左子树和右子树，并且所有的叶子都在同一层上。这样的二叉树称为满二叉树。
           3.完全二叉树。n个节点按层编号，编号顺序和同样深度的满二叉树编号为i的节点在二叉树的位置完全相同就是完全二叉树。
 
            完全---不一定是满
            满---一定是完全
 
 
 二叉树的性质
 
 
 一个深度为k的二叉树中最多有2^k-1 节点
 
 一棵非空的二叉树的第i层最多有2^(i-1)个节点
 
 对于一棵非空的二叉树，如果叶子节点数为n0，度数为2的节点数n2, 则n0=n2+1；
 
 具有n个节点的完全二叉树的深度k=|_log2（n）_|+1.
 

*/

// 二叉树的存储结构

// --存放在数组中

typedef struct XBBinTree
{
    
    int maxNum;//最大的值
    XBLinkNode * linkHeader;//空间大小是二叉树最多节点数量，一个深度为k的右斜树时需要分配2^k -1 个存储空间，浪费严重，
    //索引的位置就是节点在完全二叉树的位置。中间空的也不能省略，所以这样的结构只用来存储完全二叉树比较合理
    
}XBBinTree;
// 二叉链表--存储,最常见的

typedef struct XBBinLinkTNode
{
    DATATYPE data;
    struct XBBinLinkTNode * lChild,*rChild;
    
}XBBinLinkTNode;


XBBinLinkTNode * XBInitBinTreeNode(DATATYPE data)
{   //初始化建立二叉树
    XBBinLinkTNode * bt = (XBBinLinkTNode *)malloc(sizeof(XBBinLinkTNode));
    bt->data = data;
    bt->lChild=NULL;
    bt->rChild=NULL;
    return bt;
}


//在二叉树的左子树或者右子树的地方插入一个值,
int XBInsertTree(XBBinLinkTNode * rootNode,DATATYPE newData,int l_or_r)
{
    if (rootNode==NULL) {
        
        return NO;
    }
//   创建一个新的节点存储值
    XBBinLinkTNode * node = XBInitBinTreeNode(newData);
    
    if (l_or_r==0) {//表示在左边插入
        
        if (rootNode->lChild==NULL) {
            
            rootNode->lChild = node;
        }
        else  // 有节点就类似于链表插入
        {
            node->lChild = rootNode->lChild;
            rootNode->lChild = node;//
        }
    }
    else //表示在右边插入
    {
        if (rootNode->rChild==NULL) {
            
            rootNode->rChild = node;
        }
        else  // 有节点就类似于链表插入
        {
            node->rChild = rootNode->rChild;
            rootNode->rChild = node;//
        }
    }
    return  YES;
}

int deXBBinChildTree(XBBinLinkTNode * rootNode,int  l_or_r)
{
    
    if (rootNode==NULL) {
        return NO;
    }
    if (l_or_r==0) {
        
        XBBinLinkTNode * l =   rootNode->lChild;
        rootNode->lChild = NULL;
        free(l);
    }
    else
    {
        XBBinLinkTNode * r =   rootNode->lChild;
        rootNode->lChild = NULL;
        free(r);
    }
    return YES;
}

//返回根树的节点
/*
 
 对于具有N个节点的完全二叉树，如果按照从上到下和从左到有的顺序，
 对二叉树的所有节点从1开始按顺序编号 对于任意的序号i的节点有 1.如果i>1，
 则序号i的结点的双亲节点的序号是/2 i=1就是根结点无双亲节点 2.如果2i<=n则序号i的结点的左孩子节点的序号是2i,
 如果2*i大于n节点无左孩子 3.如果2*i+1<=n序号为i的节点的右孩子的序号2*i+1,否则i的结点无右孩子
 
 
 */

//这种方式创建二叉树利用的是二叉树的性质
XBBinLinkTNode *  createXBTree()
{
        XBBinLinkTNode *t = NULL,*p,*v[MAX_SIZE];
        printf("\n i data=?");
        int i,e,j;
        //i表示节点，e，表示节点所对应的元素
        scanf("%d %d",&i,&e);
        while(i!=0&&e!=0)
        {
            //申请一个节点
            p=(XBBinLinkTNode*)malloc(sizeof(XBBinLinkTNode));
            p->data=e;
            p->rChild=NULL;
            p->lChild=NULL;
            v[i]=p;
            if(i==1)//根节点
            {
                t=p;
            }
            else
            {
                j=i/2;//这里用的是完全二叉树的性质，左子树的左节点索引= 双亲节点索引*2 ，右节点比左节点索引大1
                if(i%2==0)
                {
                    v[j]->lChild=p;
                }
                else
                {
                    v[j]->rChild=p;
                }
            }
            printf("\n i data=?");
            scanf("%d %d",&i,&e);
        }
        return t;
}
/*模仿先序递归遍历法建立二叉树,这样建立二叉树需要给每个节点的子节点都要赋值，即使没有子节点也要赋值为0表示*/
XBBinLinkTNode *createXBT2()//对比Creat_One函数进行的递归
{ //缺点，递归不断的调用自身，不知道什么什么时候结束，对于每次调用都要对最后的节点复制0程序才知道结束
    //输入的数据是2^0+2^1+...2^n个，需要输入0来告诉程序结束的个数是2^(n+1)个
    XBBinLinkTNode *t; printf("\ndata=");
    int e;
    scanf("%d",&e);
    if(e==0)
        t=NULL;
    else
    {
        t=(XBBinLinkTNode*)malloc(sizeof(XBBinLinkTNode));
        t->data=e; t->lChild=createXBT2();/*获得新的指针值*/
        t->rChild=createXBT2();
    } return t;
}











// --- 先，中，后艮遍历，都是用了递归方式
//先根遍历
void XBTPreOrder(XBBinLinkTNode *bt)//先根序，先节点，再左边，最后右边
{
    if(bt==NULL)
        return;
    printf("%d",bt->data);
    XBTPreOrder(bt->lChild);
    XBTPreOrder(bt->rChild);
}

void XBTInOrder(XBBinLinkTNode *bt)//中序遍历根节点的左子树，访问根节点，中序遍历里节点的右子树
{
    if(bt==NULL)
    {
        return ;
    }
    XBTInOrder(bt->lChild);
    printf("%d  ",bt->data);
    XBTInOrder(bt->rChild);
}
void XBTLastOrder(XBBinLinkTNode*bt)//后序遍历根结点的左子树，后序遍历根结点的右子树，访问根节点
{
    if(bt==NULL)
    {
        return ;
    }
    XBTLastOrder(bt->lChild);
    XBTLastOrder(bt->rChild);
    printf("%d  ",bt->data);
}



// -- 层次遍历，用到的是队列，C语言里面没有泛型的知识，没有办法直接拿以前的队列用，改了以前的就不能用了

struct XBBinNodeQ
{
    XBBinLinkTNode* nodes[MAX_SIZE];
    int front;
    int rear;
};

void XBTLeveOrder(XBBinLinkTNode*bt)//层次遍历
{
    
    struct XBBinNodeQ TNODES;
    TNODES.front=-1;
    TNODES.rear =0;
    if (bt==NULL) {
        return;
    }
    TNODES.nodes[TNODES.rear]=bt;
    while(TNODES.front!=TNODES.rear)
    {
        TNODES.front++;
        printf("%d  ",TNODES.nodes[TNODES.front]->data);//访问一个节点后就把子树的节点入队列
        if(TNODES.nodes[TNODES.front]->lChild!=NULL)
        {
            TNODES.rear++;
            TNODES.nodes[TNODES.rear]=TNODES.nodes[TNODES.front]->lChild; //入队列
        }
        if(TNODES.nodes[TNODES.front]->rChild!=NULL)
        {
            TNODES.rear++;
            TNODES.nodes[TNODES.rear]=TNODES.nodes[TNODES.front]->rChild; //入队列
        }
    }
    
}

//定义一个栈
struct XBBinNodeStack
{
    XBBinLinkTNode * nodes[MAX_SIZE];
    int top;
};



/*
 
 sqstack s; BNode *p;
 s.top=0;
 push(&s,t);
 while(s.top!=0)
 {
 while(s.a[s.top]!=NULL)
 {
 p=s.a[s.top];
 push(&s,p->l_child);
 }
 p=pop(&s);
 if(s.top!=0)
 {
 p=pop(&s);
 printf("%3d",p->data);
 push(&s,p->r_child);
 }
 }

 */

// 先根遍历，非递归调用，其实也是递归用的是栈。
void XBTPrintOrderStack(XBBinLinkTNode*bt)//非递归
{
       struct  XBBinNodeStack s;
        XBBinLinkTNode *p;
        s.top=0;
        s.nodes[s.top] = bt;
        while(s.top!=0)
        {
            while(s.nodes[s.top]!=NULL)
            {
                p=s.nodes[s.top];
                s.nodes[++s.top] = p->lChild;
            }
            p=s.nodes[s.top--];
            if(s.top!=0)
            {
                p=s.nodes[s.top--];
                
                
                
                printf("%3d",p->data);
                s.nodes[++s.top]=p->rChild;
            }
        }
}
















